class Solution
{
public:
    int subarraySum(vector<int> &nums, int k)
    {
        int n = nums.size();
        vector<int> prefixSum(n + 1);
        partial_sum(nums.begin(), nums.end(), prefixSum.begin() + 1);
        int result = 0;
        unordered_map<int, int> leftPrefixSumCount;
        leftPrefixSumCount[0] = 1;
        for (int i = 1; i <= n; ++i)
        {
            if (leftPrefixSumCount.count(prefixSum[i] - k))
            {
                result += leftPrefixSumCount[prefixSum[i] - k];
            }
            ++leftPrefixSumCount[prefixSum[i]];
        }
        return result;
    }
};